#include <stdio.h>

#include "bitree.h"

// 外部变量，用于记录最大宽度
int maxWidth = 0;

// visit函数，用于更新最大宽度
void visit(BiTree t, int currentWidth) {
    if (currentWidth > maxWidth) {
        maxWidth = currentWidth;
    }
}
int Width(BiTree t) {
    if (!t) {
        return 0;
    }
    maxWidth = 1;     // 重置最大宽度，t不为空时，宽度至少为1
    BiTree last = t;  // 记录当前层的最后一个节点
    SqQueue q;
    InitQueue(&q);
    EnQueue(&q, t);  // 根节点入队
    while (!QueueEmpty(&q)) {
        BiTree p;
        DeQueue(&q, (void**)&p);  // 对头结点出队
        if (p->lchild) {
            EnQueue(&q, p->lchild);  // 如果有左孩子，将左孩子入队
        }
        if (p->rchild) {
            EnQueue(&q, p->rchild);  // 如果有右孩子，将右孩子入队
        }
        if (p == last) {  // 如果p是当前层的最后一个节点
            visit(p, QueueLength(&q));  // 使用visit函数更新宽度
            if (!QueueEmpty(&q)) {
                last = q.data[q.rear - 1];  // 更新last为下一层的最后一个结点
            }
        }
    }
    return maxWidth;
}

void TestWidth(ElemType arr[], int n) {
    printf("test begin\n");

    BiTree root;
    LevelOrderCreateBiTree(&root, arr, n);
    printf("宽度为：%d\n", Width(root));

    printf("test end\n");
}

int main() {
    ElemType arr1[] = {'A'};
    TestWidth(arr1, 1);

    ElemType arr2[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    TestWidth(arr2, 7);

    ElemType arr3[] = {'A', 'B', 'C', '#', '#', 'D', 'E', '#',
                       'F', '#', '#', 'G', '#', '#', '#'};
    TestWidth(arr3, 15);

    return 0;
}